Zhao70's Blog

PAT1045. Favorite Color Stripe

发表于 | 分类于

题目大意

1045. Favorite Color Stripe

给定两个序列 a 和 b, 求 b 中元素按照 a 的子序列中元素出现的次序 的 最大公共序列长度.

题目分析

当 a 为 0 或者 b 为 0, 则平凡态为 0

f(0, l) = f(m, 0) = 0

  • 当 两个序列当前的末尾相同, 即 a[i] == a[j], 则当前长度等于原有长度 + 1.

    f(i, j) = f(i, j - 1) + 1
    // m 相同代表末尾颜色相同, l - 1 表示先前(即长度减一)的状态.

  • 当两个序列当前的末尾不相同, 即 a[i] != a[j], 肯定不可以进行拼凑.
    所以当前状态f(i, j)的值肯定由上一个 a[i] == a[j]的状态转移而来.
    我们可以缩短a的长度来改变a的末尾元素, 即 f(i - 1, j).
    或者缩短b的长度来改变b的末尾元素, 即f(i, j - 1).

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <cstdio>
using namespace std;
const int maxm = 200 + 10;
const int maxl = 10000 + 10;
int dp[maxl];
int favo[maxm];
int stri[maxl];
int main(){
    int n, m, l;
    scanf("%*d%d", &m);
    for(int i = 1; i <= m; i++)
        scanf("%d", &favo[i]);
    scanf("%d", &l);
    for(int i = 1; i <= l; i++)
        scanf("%d", &stri[i]);
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= l; j++)
            if(favo[i] == stri[j])
                dp[j] = dp[j - 1] + 1;
            else if(dp[j] < dp[j - 1])
                dp[j] = dp[j - 1];
    printf("%d\n", dp[l]);
    return 0;
}